Codeforces Round #818 (Div. 2)

A

不妨设 ab,d=gcd(a,b)a\le b,\,d=\gcd(a,b)

a=da1,b=db1a=da_1,\,b=db_1 ,且 gcd(a1,b1)=1\gcd(a_1,b_1)=1

lcm(a,b)=da1b1\operatorname{lcm}(a,b)=da_1b_1

从而 lcm(a,b)gcd(a,b)=a1b13\dfrac{\operatorname{lcm}(a,b)}{\gcd(a,b)}=a_1b_1\le 3 ,一共只有 33 种情况,讨论一下即可。

Code

#include <cstdio>

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        printf("%d\n", (n / 2 + n / 3) * 2 + n);
    }
}

B

容易发现排列是有周期性的,只需要处理 k×kk\times k 的方格表,循环输出即可。

Code

#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 505;

char mp[N][N];
int T, n, k, r, c;

void solve() {
    scanf("%d%d%d%d", &n, &k, &r, &c);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            mp[i][j] = '.';
    }
    r = (r - 1) % k + 1;
    c = (c - 1) % k + 1;
    for (int i = 1; i <= k; i++) {
        mp[r--][c++] = 'X';
        if (r == 0) r = k;
        if (c == k + 1) c = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            putchar(mp[(i - 1) % k + 1][(j - 1) % k + 1]);
        puts("");
    }
}

int main() {
    scanf("%d", &T);
    while (T--) solve();
}

C

后面我都不会做了

首先必须要求 biaib_i\ge a_i ,否则必然不可行。

由于数列是环状的,不妨破环成链,令 an+1=a1,bn+1=b1a_{n+1}=a_1,\,b_{n+1}=b_1

结论:aa 能变换到 bb 等价于对于任意 ii ,有 ai=bia_i=b_ibibi+1+1b_i\le b_{i+1}+1

先证充分性。考虑将 aia_i 变换至 bib_i 的最后一次操作,若 ai=bia_i=b_i 则不用变换,否则必然是 ai=bi1a_i=b_i-1ai+1bi+1a_{i+1}\le b_{i+1}

由于此时 aiai+1a_i\le a_{i+1} ,故有

bi1ai+1bi+1b_i-1\le a_{i+1}\le b_{i+1}

从而 bibi+1+1b_i\le b_{i+1}+1

再证必要性。考虑每一轮变换 ai=minjaja_i=\min\limits_{j}{a_j} ,则 ai<bibi+1+1a_i \lt b_i \le b_{i+1}+1 ,故我们必然可以让 aia_i 进行一次变换,易知可以持续操作直至 a=ba=b

所以只需要判断两种情况即可,时间复杂度 O(n)O(\sum n)

Code

#include <cstdio>
#include <cstring>

const int N = 4e5 + 5;

int a[N], b[N], n, T;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            a[i + n] = a[i];
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d", &b[i]);
            b[i + n] = b[i];
        }
        bool flag = 1;
        for (int i = 1; i <= n; i++) {
            if (b[i] < a[i])
                flag = 0;
        }
        if (!flag) {
            puts("NO");
            continue;
        }
        flag = 1;
        for (int i = 1; i <= n; i++) {
            if (b[i] > b[i + 1] + 1 && a[i] != b[i])
                flag = 0;
        }
        puts(flag ? "YES" : "NO");
    }
}

D

以下内容来源于题解

考虑对于每个人到根节点的路径,将每条边的胜负分别对应 1/01/0 ,得到一个长度为 nn 的二进制数,可以证明这样的 2n2^n 个二进制数和树上 2n2^n 个叶节点一一对应,不妨设 f(x)f(x) 表示叶节点 xx 对应的二进制数。

我们考虑判断某个节点 uu 是否可以通过不超过 kk 调整使得 uu 最终获胜,即每次在 f(u)f(u) 中修改一位的值,最终能否使 f(u)f(u) 全部为 11 ,不难发现这个问题等价于使得 f(u)f(u) 中的 00 的个数不超过 kk ,显然,最终状态就是所有这样的 uu 的最大值。

注意到所有 ff 值中有 ii 位为 00 的有 (ni)\binom{n}{i} 个,即答案为

i=0min{n,k}(ni)\sum\limits_{i=0}^{\min\{n,k\}}\dbinom{n}{i}

时间复杂度 O(min{n,k})O(\min\{n,k\})

Code

#include <algorithm>
#include <iostream>
using namespace std;

typedef long long int64;

const int N = 1e5 + 5;
const int64 mod = 1e9 + 7;

int64 fac[N], inv[N], n, k, ans;

inline int64 pow(int64 a, int64 b) {
    int64 res = 1;
    for (; b; b >>= 1, a = a * a % mod) if (b & 1) res = res * a % mod;
    return res;
}

int64 binom(int64 x, int64 y) {
    return 1LL * fac[x] * inv[y] % mod * inv[x - y] % mod;
}

int main() {
    cin >> n >> k;
    fac[0] = inv[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = pow(fac[i], mod - 2);
    }
    for (int i = 0; i <= min(n, k); i++) ans = (ans + binom(n, i)) % mod;
    cout << ans << endl;
}

E

考虑枚举 cc ,此时有

gcd(a,b)=gcd(a,a+b)=gcd(a,nc)\gcd(a,b)=\gcd(a,a+b)=\gcd(a,n-c)

d=gcd(a,b)d=\gcd(a,b) ,则 ddncn-c 的约数。

a=da1,b=db1a=da_1,\,b=db_1 ,且 gcd(a1,b1)=1\gcd(a_1,b_1)=1 ,则 a+b=d(a1+b1)a+b=d(a_1+b_1) ,易知 gcd(d,a1+b1)=1\gcd(d,a_1+b_1)=1 ,从而满足要求的数对 (a,b)(a,b) 的个数为 φ(ncd)\varphi(\frac{n-c}{d})

于是答案为

c=1n2d(nc)lcm(c,d)×φ(ncd)\sum\limits_{c=1}^{n-2}\sum\limits_{d\mid (n-c)}\operatorname{lcm}(c,d)\times\varphi\left(\frac{n-c}{d}\right)

预处理 10510^5 以内每个数的 φ\varphi 值和所有约数,时间复杂度 O(nlogn)O(n\log{n})

Code

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

const int N = 1e5 + 5;
const int mod = 1e9 + 7;

int prime[N], vis[N], phi[N], n, cnt, ans;

inline void sieve() {
    vis[1] = 1;
    for (int i = 2; i < N; i++) {
        if (vis[i] == 0) {
            prime[++cnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= cnt && i * prime[j] < N; j++) {
            vis[i * prime[j]] = 1;
            if (i % prime[j]) {
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
            } else {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
        }
    }
}

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

vector<int> f[N];

void factor() {
    for (int i = 1; i < N; i++) {
        for (int j = i; j < N; j += i)
            f[j].push_back(i);
    }
}

int main() {
    scanf("%d", &n);
    sieve();
    factor();
    for (int c = 1; c <= n - 2; c++)
        for (int d: f[n - c]) {
            int lcm = 1LL * c * d / gcd(c, d) % mod;
            ans = (ans + 1LL * lcm * phi[(n - c) / d] % mod) % mod;
        }
    printf("%d\n", ans);
}

F

待补。

赞赏